/**
 * 
 */
package array.passed;

/**
 * @author xyyi
 *
 */
public class TrappingRainWater {

	/**
	Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

	For example,
	Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
	 */
	public int trap(int[] A) {
		if (A == null || A.length == 0)
			return 0;

		int maxIndex = 0;
		for (int i = 1; i < A.length; i++) {
			if (A[i] > A[maxIndex]) {
				maxIndex = i;
			}
		}

		int result = 0, high = 0;
		for (int i = 0; i < maxIndex; i++) {
			if (high > A[i])
				result = result + high - A[i];
			else
				high = A[i];
		}
		high = 0;
		for (int i = A.length - 1; i > maxIndex; i--) {
			if (high > A[i])
				result = result + high - A[i];
			else
				high = A[i];
		}

		return result;
	}

	/**
	 * 
	 */
	public TrappingRainWater() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
